function lowbit(a){
    return a & (a ^ (a-1));
  }
  function lowbit(a){
    return a&(~a+1);
  }
  function lowbit(a){
    return a&(-a);
  }
//   console.log( lowbit(13));  // 1101  -> 1 -> 2 ^ 1 -> 1
//   console.log( lowbit(8));   // 1000  -> 2^3 -> 8
//   console.log( lowbit(4));   // 100   -> 2^2 -> 4
//   console.log( lowbit(1));   // 0     -> 2^0 -> 1
//   console.log( lowbit(18));  // 10010 -> 10 -> 2^1 -> 2

// function getChildSet(x){
//     var start = x;
//     // 获得一个数的子集
//     var set = [];
//     while(x){
//       var v = lowbit(x);
//       set.push(v);
//       x = x -v;
//     }
//     console.log( start+" -> "+ set);
//     return set;
//   }
//   getChildSet(1);
//   getChildSet(2);
//   getChildSet(3);
//   getChildSet(4);
//   getChildSet(5);
//   getChildSet(6);
//   getChildSet(7);
//   getChildSet(8);
//   getChildSet(9);
//   getChildSet(10);

//   function getParent(x){
//     var bit = lowbit(x);
//     console.log(x, bit, 'bit');
//     return x === bit ? x : x + bit;
//   }
//   console.log(getParent(7)); // 7+1 = 8
//   console.log(getParent(6)); // 6+2 = 8
//   console.log(getParent(4)); // 4+4 = 8

// function getChildNodes(x){
//     var nodes = [];
//     for(var i = 1; i < x; i++){
//       if(i + lowbit(i) === x){
//         nodes.push(i);
//       }
//     }
//     nodes.push(x);
//     console.log(x+" has "+ nodes);
//     return nodes;
//   }
// getChildNodes(8); // 8 has 4、6、7、8

// function getChildNodes(x){
//     var nodes = [], old = x;
//     var z = x - lowbit(x); 
//     nodes.push(x); 
//     x--; // 去掉它本身
//     while (x != z) {
//       nodes.push(x);
//       x -= lowbit(x);// 求得它的孩子结点
//     }
//     console.log(old+" has "+ nodes);
//     return nodes;
//   }
// getChildNodes(8); // 8 has 4、6、7、8

// 9.2　构建

// function prefixSum(x, c){
//     var z = x - lowbit(x); 
//     var sum = 0;
//     x--; // 去掉它本身
//     while (x != z) {
//       sum += c[x];
//       x -= lowbit(x);// 求得它的孩子结点
//     }
//     return sum;
//   }
  
//   class BinaryIndexedTree{
//     constructor(array) {
//     //   var n = array.length;
//     //   this.length = n;
//     //   this.c = new Array(n + 1).fill(0);
//     //   for (var i = 0; i < n; i++) {
//     //     this.c[i+1] = array[i] + prefixSum(i+1, this.c);
//     //     // 构建子集和数组
//     //   }
//         var n = array.length;
//         this.length = n;
//         this.c = new Array(n + 1).fill(0);
//         for (var i = 0; i < n; i++) {
//         this.add(i+1, array[i]); // 构建子集和数组
//         }
//     }
//     get(index) {
//         if (index < 1 && index > this.length) {
//           throw new RangeError("Out of Range!");
//         }
//         return this.c[index] - prefixSum(index, this.c);
//     }
//     add(index, delta) {
//         while(index <= this.length){
//           this.c[index] += delta;
//           index += lowbit(index);// 求其父结点
//         }
//     }
//     set(index, value) {
//         var diff = value - this[c];
//         this.add(index, diff);
//     }
//     sum(n) {
//         if (n < 1 && n > this.length) {
//           throw new RangeError("Out of Range!");
//         }
//         var ret = 0;
//         while (n > 0) {
//           console.log("跳到"+n+"位置上");// only test
//           ret += this.c[n];
//           n -= lowbit(n);
//         }
//         return ret;
//     }
//     rangeSum(a, b) {
//         return this.sum(b) - this.sum(a - 1);
//     }
//     rangeAdd(a, b, delta) {
//         this.add(a, delta);
//         this.add(b + 1, -delta);
//     }
//   }
  
//   var t = new BinaryIndexedTree([10, 18, 12, 5, 7, 11, 4, 15]);
  
//   console.log(t.c); // 10,28,12,45,7,18,4,82
    /**
     *  10
     *  28 = 10+18
     *  12
     *  45 = 28+12+5
     *  7
     *  18 = 7+11
     *  4
     *  82 = 45+18+4+15
     */

//  9.3　单点查询
// var t = new BinaryIndexedTree([10, 18, 12, 5, 7, 11, 4, 15]);
// console.log(t.c); // 10,28,12,45,7,18,4,82
// console.log(t.sum(7));



// 9.8　区间最值
// class BinaryIndexedTree{
//     constructor(array) {
//       var n = array.length;
//       this.length = n;
//       this.c = new Array(n + 1).fill(0);
//       this.h = new Array(n + 1).fill(-Infinity);
//       for (var i = 0; i < n; i++) {
//         this.add(i+1, array[i]); // 构建子集和数组
//         this.calcMax(i+1, array[i])
//       }
//     }
//     calcMax(x, value){
//       while (x <= this.length) {
//           this.h[x] = Math.max(this.h[x], value); 
//           x += lowbit(x);
//       }
//     }
// }
// class BinaryIndexedTree{
//     constructor(array) {
//       var n = array.length;
//       this.length = n;
//       this.c = new Array(n + 1).fill(0);
//       this.a = [0].concat(array);// 将有效数据后挪一位，这样我们能从1数起
//       this.h = new Array(n + 1).fill(-Infinity);
//       for (var i = 0; i < n; i++) {
//         this.add(i+1, array[i]); // 构建子集和数组
//         this.calcMax(i+1);
//       }
//     }
//     calcMax(x){
//       var h = this.h, a = this.a;
//       for(var i = x; i <= this.length; i+= lowbit(i)){
//           h[i] = a[i];
//           for (var j=1; j< lowbit(i); j<<=1){
//             h[i] = Math.max(h[i], h[i-j] );
//       }
//       }
//     }
//     modifyMax(x, value){
//         this.a[x] = value, h = this.h;
//           for(var i = x; i <= this.length; i += lowbit(i)){
//             h[i] = Math.max(h[i], value); 
//             for(var j = 1; j < lowbit(i); j <<= 1){          
//               h[i] = Math.max(h[i], h[i-j]);
//             }
//         }
//     }
//     add(index, delta) {
//         while(index <= this.length){
//           this.c[index] += delta;
//           index += lowbit(index);// 求其父结点
//         }
//     }
//     queryMax (x,  y) {
//         var h = this.h;
//         var ret = 0;
//         while (y >= x) {  
//           ret = Math.max (ret, this.a[y]);
//           // 如果x还没有到y时，那么我们找到y的孩子结点，比较两者的峰值
//           for(y -= 1; y-lowbit(y) >= x; y -= lowbit(y)){
//             ret = Math.max(ret, h[y]);
//           }
//         }
//         return ret;
        
//     }
// }

// 9.10　数组离散化

// var nums = [1000, 65, 32, 1200, 78];
// function discretize(nums){
//   var dispersed = nums.concat();
//   nums.sort(function (a, b) {
//     return a - b;
//   });
//   var hash = [];
//   nums.forEach(function (el, i) {
//     hash[el] = i;
//   });

//   dispersed.forEach(function (el, i) {
//     dispersed[i] = hash[el];
//   });
//   return dispersed;
// }

// console.log(discretize(nums));

function discretize(nums) {
    var dispersed = nums.concat();
    nums.sort(function (a, b) {
      return a - b;
    });
    var hash = [];
    nums.forEach(function (el, i) {
      hash[el] = i + 1; // 注意，索引值不能为零，否则lowbit(0) == 0
    });
    dispersed.forEach(function (el, i) {
      dispersed[i] = hash[el];
    });
    return dispersed;
  }
  function add(c, index, delta) {
    while (index <= c.length) {
      c[index] += delta;
      var old = index;
      index += lowbit(index);// 求其父结点
      if (old == index) {
        console.log(index, '不能为0');
        break;
      }
    }
  }
  function sum(c, n) {
    var ret = 0;
    while (n > 0) {
      ret += c[n];
      n -= lowbit(n);
    }
    return ret;
  }
//   var nums = [1, 4, 2, 3, 5];
//   var a = discretize(nums);
//   var n = a.length;
//   var c = new Array(n).fill(0);// 树状数组
//   var ans = 0;
//   for (var i = n; i > 0; --i) {
//     add(c, a[i], 1);
//     ans += sum(c, a[i] - 1);
//   }
//   console.log(ans);
// discretize、lowbit、add和sum等略
var nums = [1, 4, 2, 3, 5];
var a = discretize(nums);
var n = a.length;
var c = new Array(n).fill(0);// 树状数组
var ans = 0;
for (var i = 0; i < n; i++) {
  add(c, a[i], 1);
  ans += i - sum(c, a[i] - 1);
}
console.log(ans);